Spreadsheets are a well-known means for processing numeric information wherein particular cells in the spreadsheet may be related with known mathematical relationships. An example of a spreadsheet application is the EXCEL spreadsheet, available from Microsoft Corporation. Basic spreadsheet-type programs have been extended to other applications, for example project management types of computer programs such as the Microsoft PROJECT application program. In project management type programs, the cells of the spreadsheet contain information related to a task or a resource allotted to a task. For purposes of this discussion, the term "spreadsheet" will be used for both numeric-oriented types of applications as well as project management-oriented or other types of applications.
Many computer application programs have the ability to display an expanded array of cell border, background, and character attribute information wherein data is displayed to the user with the same format attributes in which printed data will appear. For example, characters may typically be printed with any of a number of fonts wherein characters may be bold, underlined, italicized, centered, etc. Similarly, individual cells may be displayed with various borders and background colors.
In prior spreadsheet applications, format attribute information was stored in memory. Therefore, for each spreadsheet cell, several bytes of information were required. For example, for each character, individual data bytes were required for the character data values, as well as for attribute information, such as fonts; and position enhancements as mentioned above, e.g., superscript, centered, left justified, etc.; and appearance or "style", such as bold and italics. In prior systems, where relatively small amounts of data were processed, this arrangement provided acceptable performance and utility. However, as computer systems have become more sophisticated, the size and complexity of programs has increased dramatically. The increased amount of data processed in applications such as spreadsheets, coupled with the desirability of providing enhanced character attributes, has rapidly increased the memory needed to support an application. Therefore, techniques which improved speed, efficiency and performance of computer application programs have become increasingly important.
There are two particular difficulties in display formatting for spreadsheet type applications--memory usage considerations and performance considerations. In the Microsoft PROJECT application, as many as 10,000 different tasks and resources can be tracked in a project. Each task can have 114 fields associated therewith, thereby generating over a million data entries (114.times.10,000=1,114,000). Even if a project data file only utilized 10 bytes per entry for formatting information, more than 10 megabytes of memory would be required. But even 10 bytes per entry is insufficient when considering that a font name, font size, styles, color, etc. must be accommodated.
The large amounts of data that must be handled also raise performance issues. In a project management type spreadsheet, a task can be moved around, and it is generally desired that the task retain its formatting rather than adopt the formatting of a location to which the task is moved. Each time a cell is "painted" in the spreadsheet (e.g. by displaying the data on a display screen in response to a screen updating event such as screen resizing, screen repositioning, etc.), the computer system must locate the data and formatting information for the cells to be displayed, which will not necessarily be in a sequential order. Thus, a search of some type must be employed to find the data and formatting information.
One approach to improved handling of formatting information in a spreadsheet is described in U.S. Pat. No. 5,231,577 to Koss, which assigned to the same assignee as the present invention. In this patent, the formatting information is stored in an extended format table comprising a linked list of extended format combinations. When a new extended format combination is created, its position in the extended format table is calculated according to a predetermined hash function. If two extended format combinations hash to the same location, the conflicting extended format is placed in an overflow table. Each cell in the spreadsheet contains an internal index which references a cell to an entry in the extended format table. Character format information is not stored in individual cells, and cells may share the same format combinations by merely setting the cell index to point to a desired format combination.
While this arrangement results in improvements because less memory is required, in certain cases a search of a data array using a hash function take a long time, resulting in display screen refresh delays which are annoying to users. Use of a hash function for searching requires handling of possible duplicative results of the hash function, hence the provision of the overflow table. In degenerate cases, a search with a hash function might required as many memory accesses as there are entries in the table.
The approach to formatting shown in the referenced '577 patent does not permit a task or column of fields to be moved yet retain the original formatting. If a row or column of data in many numeric oriented spreadsheets is moved from one location to another (which is a common operation in spreadsheets), the moved row or column adopts the formatting associated with the region into which it is moved, e.g. if row 3 is moved to row 15, row 3 becomes row 15 and takes on the formatting of row 15; the original formatting for row 3 is lost. As mentioned, for a project management type application, it is generally preferred that a moved row or column maintain the associated formatting if the row or column is moved.
A critical performance characteristic of spreadsheet type applications is the "refresh" time, that is, the speed with which the program can repaint the display screen after a user command is issued or an internal refresh-triggering event occurs. Although the use of a separate format table, as in the above-mentioned '577 patent, is a significant step toward memory savings in spreadsheet type application, there is room for further improvement in the speed for retrieving data and formatting information for output to a display device such as a display monitor. Moreover, since the '577 patent provides no mechanism for memory savings when formatting is to be applied to an entire row or column, there is room for further improvement in memory usage of formatting features in spreadsheet and other types of applications.